import java.util.*;

public class SlidingWindowMaximum {
    public static List<Integer> maxInSlidingWindow(int[] num, int size) {
        List<Integer> result = new ArrayList<>();
        if (num == null || num.length == 0 || size == 0 || size > num.length) {
            return result;
        }

        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < num.length; i++) {
            // 移除不在滑动窗口范围内的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - size + 1) {
                deque.pollFirst();
            }

            // 移除比当前元素小的所有元素，以保持队列递减
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.pollLast();
            }

            // 添加当前元素的下标
            deque.offerLast(i);

            // 当窗口大小达到 size 时，记录当前窗口的最大值
            if (i >= size - 1) {
                result.add(num[deque.peekFirst()]);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] num = {2, 3, 4, 2, 6, 2, 5, 1};
        int size = 3;
        List<Integer> maxValues = maxInSlidingWindow(num, size);
        System.out.println(maxValues); // 输出 [4, 4, 6, 6, 6, 5]
    }
}
